/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/search-in-rotated-sorted-array-ii
   @Language: C++
   @Datetime: 19-06-04 17:35
   */

// Method 1, Time 16ms
class Solution {
public:
	bool search(vector<int>& nums, int target) {
		int n=nums.size(), pos=0;
		if(n==0) return false;
		for(pos=0; ++pos<n;){
			nums.push_back(nums[pos-1]);
			if(nums[pos-1]>nums[pos]) break;
		}
		if(pos==n) pos=0;
		auto i=lower_bound(nums.begin()+pos,nums.end(),target);
		return (i!=nums.end() && *i==target);
	}
};

// Method 2, Time 8ms
class Solution {
public:
	bool search(vector<int>& nums, int target) {
		unordered_set<int> dict(nums.begin(),nums.end());
		return dict.count(target);
	}
};
